package com.zx._12_算法.数据结构.array;

import java.util.Arrays;

//给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
/*
	示例 1:
		输入: [1,2,3,4,5,6,7] 和 k = 3
		输出: [5,6,7,1,2,3,4]
		解释:
		向右旋转 1 步: [7,1,2,3,4,5,6]
		向右旋转 2 步: [6,7,1,2,3,4,5]
		向右旋转 3 步: [5,6,7,1,2,3,4]
	
	示例 2:
		输入: [-1,-100,3,99] 和 k = 2
		输出: [3,99,-1,-100]
		解释: 
		向右旋转 1 步: [99,-1,-100,3]
		向右旋转 2 步: [3,99,-1,-100]
	
	说明:
		尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
		要求使用空间复杂度为 O(1) 的原地算法。
*/
public class Demo4 {

    public static void rotate(int[] nums, int k) {
        if (nums == null) {
            return;
        }

        if (nums.length == 0 || nums.length == 1) {
            return;
        }

        int len = nums.length;
        k = k % len;// 防止k值过大

        if (k == 0) {// k是len的倍数，等于没有移动
            return;
        }
        //保存原有数组的值
        Integer[] temp = new Integer[len];

        for (int i = 0; i < len; i++) {
            int idx = i + k;//移动后的索引
            if (idx >= len) {
                idx -= len;
            }

            if (temp[idx] == null) {
                temp[idx] = nums[idx];
            }

            if (temp[i] == null) {
                temp[i] = nums[i];
            }
            nums[idx] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] n1 = {1, 2, 3, 4, 5, 6, 7};
        int k1 = 3;
        rotate(n1, k1);
        System.out.println(Arrays.toString(n1));

        int[] n2 = {-1, -100, 3, 99};
        int k2 = 2;
        rotate(n2, k2);
        System.out.println(Arrays.toString(n2));

        int[] n3 = {1, 2, 1};
        int k3 = 2;
        rotate(n3, k3);
        System.out.println(Arrays.toString(n3));
    }
}
